package com.itheima.shu_zu_kuai_pai;

public class Demo01 {
    public static void main(String[] args) {
        /**
         * 1.从右开始找比基准数小的
         * 2.从左开始找比基准数大的
         * 3.交换两个值的位置
         * 4.红色继续往左找，蓝色继续往右找，直到两个索引值相同为止
         * 5.基准数归位
         */
        int[] arr = {6,1,2,7,9,3,4,5,10,8};
        quickSort(arr,0,arr.length - 1);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "  ");
        }
    }

    private static void quickSort(int[] arr, int left, int right) {
       int left0 = left;
       int right0 = right;

       //定义基准数
        int baseNum = arr[left0];

        while(left != right){
            //1.从右开始找比基准数小的
            while(arr[right] >= baseNum && left < right){
                right --;
            }
            //2.从左开始找比基准数大的
            while(arr[left] <= baseNum && left < right){
                left ++;
            }
            //3.交换两个值的位置
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
        //基准数归位
        int temp = arr[left];
        arr[left] = arr[left0];
        arr[left0] = temp;

    }
}
